package lc;
import java.util.*;
import org.junit.*;
public class Ex763 {

    class Solution {   
        public List<Integer> partitionLabels(String s) {
            Map<Character, int[]> map = new HashMap<>(); //字母的上下区域
            char[] cs = s.toCharArray();
            int n = cs.length;
            for (int i = 0; i < n; i++) {
                int[] cur = map.get(cs[i]);
                if (cur == null) {
                    cur = new int[2];
                    cur[0] = i;
                    map.put(cs[i], cur);
                } else {
                    cur[1] = i;
                }
            }
            //当前这片最低下标和最高下标的下一个位置
            int start = 0, end = 1;
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int[] cur = map.get(cs[i]);
                end = Math.max(end, cur[1] + 1);
                if (i == end - 1) {
                    res.add(end - start);
                    start = end;
                    end++;
                }
            } 
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.partitionLabels("ababcbacadefegdehijhklij"));        
    }

    class Solution1 {
        int n;
        Map<Character, int[]> map;
        public List<Integer> partitionLabels(String s) {
            map = new HashMap<>(); //字母的上下区域
            char[] cs = s.toCharArray();
            n = cs.length;
            for (int i = 0; i < n; i++) {
                int[] cur = map.get(cs[i]);
                if (cur == null) {
                    cur = new int[2];
                    cur[0] = i;
                    map.put(cs[i], cur);
                } else {
                    cur[1] = i;
                }
            }

            int lo = 1; //每片最少可以放一个字符
            int hi = n; //每片最多可以放n个字符

            while (lo < hi) {
                int mid = (hi - lo) / 2 + lo;
                int cnt = count(cs, mid);

            }


            List<Integer> res = new ArrayList<>();
            return res;
        }

        //计算每片最多划分m个字符需要几片
        private int count(char[] cs, int m) {
            Set<Character> set = new HashSet<>();
            int cur = 0, cnt = 1; //至少需要1片
            for (int i = 0; i < n; i++) {
                if (!set.contains(cs[i])) {
                    cur++;
                }
                if (cur == m && i < n - 1) {
                    cnt++;
                    cur = 0;
                    set = new HashSet<>();
                }
            }
            return cnt;
        }
    }
}
